#ifndef CALCULATOR_H_
#define CALCULATOR_H_
#include<iostream>
#include<stack>
#include<cmath>
#include<string>
#include<queue>

using namespace std;
class ExpressionTree
{

private:
    struct Node
    {

        string ele;
        Node* left;
        Node* right;

        Node(string value):ele{value},left{nullptr},right{nullptr}{}
        Node():left{nullptr},right{nullptr}{}

    };
    stack<char> op;    ///操作符栈,char可以直接传值给string变量
    stack<Node*> exp;   ///表达式栈
    queue<string> postfixExp;   ///存放后序表达式的队列 
    string str;   ///读入表达式
    Node * root;
    
    int OpPriority(char ch)
    {
        if(ch=='+'||ch=='-')
            return  0;
        else if(ch=='*'||ch=='/')
            return 1;
        else if(ch=='^')
            return 2;
        else if(ch=='(')
            return -1;  
        else return -2;  ///不会执行的语句，近视为了不让waring出现
    }
    bool isOperator(char ch)
    {
        return (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'||ch=='(');
    }
    void getExpression()
    {
    	if(exp.size()==1&&op.empty())
    	{
    		root=exp.top();
    		return;
		}
		else if(exp.size()==1&&!op.empty())
		{
			cerr<<"输入错误"<<endl;
			exit(-1); 
		}
        char ch=op.top();
        string s;
        s.insert(0,1,ch);
        op.pop();
		Node* p1=exp.top();
		exp.pop();
		Node* p2=exp.top();
        exp.pop();
        Node * p=new Node(s);
        p->left=p2;
        p->right=p1;
        exp.push(p);
        root=p;
    }
    
    void postfixTraverse(Node *ptr)   ///前序输出函数
    {
        if(ptr==nullptr)
            return;
        postfixTraverse(ptr->left);
        postfixTraverse(ptr->right);
		postfixExp.push(ptr->ele); 
    }
    
	double Transform(string str)   ///把字符串转换为浮点数 
	{
    	double number=0; 
    	int flag=0,k=0; //判断是否是负数 
    	if(str[0]=='-')
    	{
    		flag=1;
    		k++;
		}
		while(k<str.length()&&str[k]!='.')
		{
			number=10*number+str[k]-'0';
			k++;
		}
		if(str[k]=='.')
		{
			int i=1;
			k++;
			while(k<str.length())
			{
				number+=pow(0.1,i)*(str[k]-'0');
				i++;k++;
			}
		}
		if(flag)
			number=-number;
		return number;
	}
	
	double Calculate(double number1,double number2, string c)
	{
		switch (c[0]){
			case '+':return number1+number2;break;
			case '-':return number1-number2;break;
			case '*':return number1*number2;break;
			case '/':
				if(number2==0)
				{
					cerr<<"错误: 除数为0"<<endl;
					exit(-1);
				}
				else return number1/number2;break;
			case '^':return pow(number1,number2);break;
			default:break;
				
			}
						 
	}
	
public:
    ExpressionTree():root{nullptr}{}
    ~ExpressionTree(){}

    void ConstructTree()
    {
        string number;
        int isminus=0;///判断数字是否为负数
        int flag=0;///判断是否为需要多个字符组成的数     
        int i=0;///用于遍历
        cin >> str;
        int parenthesis=0;  ///用于判断左括号和右括号个数是否匹配
        if(str[0]=='-')
        {
            isminus=1;
            i++;
        }
        while(i<str.length())
        {
            if(str[i]=='(')
            {
                isminus=0;
                if(str[i+1]=='-')
                {
                    isminus=1;
                    i++;
				}
                op.push('(');
                parenthesis++;
            }
            else if(str[i]==')')
            {
            	parenthesis--;
            	if(str[i-2]=='(')
            	{	
            		op.pop();
				}
				else
				{
                	while(!op.empty()&&op.top()!='(')
                	{
                    	getExpression();
                	}
                	if(op.empty())
                	{
                    	cerr<<"错误: 括号不匹配"<<endl;
                    	exit(-1);
                	}
                	if(!op.empty()&&op.top()=='(')
                	{
                    	op.pop();
                	}	
            	}

            }
            else if(!op.empty()&&isOperator(str[i])&&OpPriority(str[i])>OpPriority(op.top()))
            {   ///比栈顶操作符次序高，则入栈
                isminus=0;
                op.push(str[i]);
            }
            else if(!op.empty()&&isOperator(str[i])&&OpPriority(str[i])<=OpPriority(op.top()))
            {   ///比栈顶操作符次序高，则栈顶出栈
                isminus=0;
                while(!op.empty()&&OpPriority(str[i])<=OpPriority(op.top()))
                {
                    getExpression();
                }
                op.push(str[i]);
            }
            else if(op.empty()&&isOperator(str[i]))
            {///栈为空，直接入栈
            	isminus=0;
                op.push(str[i]);
            }
            else if(str[i]>='0'&&str[i]<='9')
            {
                int k=0;
                if(isminus)///判断是否是一个负数，
                {
                    number.insert(k,1,'-');
                    k++;
                }
                while((str[i]>='0'&&str[i]<='9')||str[i]=='.')
                {
                    if(str[i]>='0'&&str[i]<='9')
                    {///将数字字符逐个读入
                        number.insert(k,1,str[i]);
                    }
                    else if(str[i]=='.')
                    {///小数点的情况
                        if(str[i+1]>='0'&&str[i]<='9')
                        number.insert(k,1,str[i]);
                    }
                    else
                    {
                        cerr<<"输入错误"<<endl;///如果小数点后无数字，则报错
                        exit(-1);
                    }
                    k++;i++;
                }
                Node* p=new Node(number);
                exp.push(p);
                number.clear();
                i--;
            }
            else
            {
            	cout<<"输入错误"<<endl;
				exit(-1);
			}
			i++;
        }
        if(parenthesis!=0)
        {
            cerr << "错误:括号不匹配！"<< endl;
            exit(-1);
        }
        while(!op.empty())
        {
            getExpression();
            if(!op.empty()&&exp.size()==1)
            {
                cerr<<"输入错误"<<endl;//表达式栈只剩下一个元素但是运算符栈仍有元素
                exit(-1);
            }

        }
        if(op.empty()&&!exp.empty())
        {
        	if(exp.size()>1)
        	{	
        		cerr<<"输入错误"<<endl;
			exit(-1);
		}	
        	getExpression();
	}
    }
        
    
    void getValue()
    {
    	postfixTraverse(root);
    	string tmp;
    	double value1=0,value2=0,value3=0;
    	stack<double> value;  ///存放数值的栈 
    	while(!postfixExp.empty())
    	{
    		tmp=postfixExp.front();
    		postfixExp.pop();///弹出第一个元素 
    		if(!(isOperator(tmp[0]))||tmp[1])   ///不是运算符就推进数值栈里 
    		{
    			value.push(Transform(tmp));
			}
			else
			{
				value1=value.top();
				value.pop();
				value2=value.top();
				value.pop();
				value3=Calculate(value2,value1,tmp);
				value.push(value3);
			}
		}
		cout<<str<<'='<<value.top()<<endl;
		
	}

    
};


#endif
